//#include <bits/stdc++.h>
//
//using namespace std;
//
//const int N=500*500+10;
//
//int m,n,pos;
//int fa[N];
//struct node
//{
//	int x,y,z;
//}a[N];
//
//bool cmp(node& a,node& b)
//{
//	return a.z<b.z;
//}
//
//int find(int x)
//{
//	return x==fa[x]?x:fa[x]=find(fa[x]);
//}
//
//int KrusKal()
//{
//	sort(a+1,a+1+pos,cmp);
//	int ret=0;
//	int cnt=0;
//	for(int i=1;i<=pos;i++)
//	{
//		int x=a[i].x,y=a[i].y,z=a[i].z;
//		int fx=find(x),fy=find(y);
//		if(fx!=fy)
//		{
//			fa[fx]=fy;
//			ret+=z;
//			cnt++;
//		}
//	}
//	ret+=(n-cnt)*m;
//	return ret;
//}
//
//int main() 
//{
//	cin>>m>>n;
//	for(int i=1;i<=n;i++)
//	{
//		for(int j=1;j<=n;j++) 
//		{
//			int x;cin>>x;
//			if(j>=i||x>m||x==0) continue;
//			pos++;
//			a[pos].x=i;a[pos].y=j;a[pos].z=x;
//		}
//	}
//	
//	for(int i=1;i<=n;i++) fa[i]=i;
//	int ret=KrusKal();
//	cout<<ret<<endl; 
//	return 0;
//}


#include <bits/stdc++.h>

using namespace std;

const int N=510,INF=0x3f3f3f3f;

int m,n;
int dist[N];
bool st[N];
vector<pair<int,int>> edges[N];

int prime()
{
	memset(dist,0x3f,sizeof dist);
	dist[1]=m;
	int ret=0;
	int cnt=0;
	for(int i=1;i<=n;i++)
	{
		int t=0;
		for(int j=1;j<=n;j++)
		{
			if(!st[j]&&dist[j]<dist[t]) t=j;
		}
		if(dist[t]==INF) break;
		
		cnt++;
		st[t]=true;
		ret+=dist[t];
		for(auto& e:edges[t])
		{
			int a=e.first,b=e.second;
			dist[a]=min(dist[a],b);
		}
	}
	ret+=m*(n-cnt);
	return ret; 
}

int main() 
{
	cin>>m>>n;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++) 
		{
			int x;cin>>x;
			if(x==0||x>m) continue; 
			edges[i].push_back({j,x});
		}
	}
	int ret=prime();
	cout<<ret<<endl; 
	return 0;
}
